#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {

        if (digits == "")
            return res;

        findCombination(digits, 0, "");

        return res;
    }

    vector<vector<int>> permute(vector<int>& nums) {
        results.clear();
        if (nums.size() == 0)
            return results;
        vector<int> p;
        used = vector<bool>(nums.size(), false);

        cout<<"Begin Debug"<<endl;
        generatePermutation(nums, 0, p);

        cout<<"End Debug"<<endl;

        return results;
    }

private:

    vector<vector<int>> results;
    vector<bool> used;
    void generatePermutation(const vector<int>& nums, int index, vector<int>& p){
        cout<<"Debug Detail: index "<<index<<endl;
        if (index == nums.size()){
            results.push_back(p);
            return;
        }
//        used = vector<bool>(nums.size(), false);
        for (int i = 0; i < nums.size(); i++) {
            cout<<"Loop Detail: "<<i<<" "<<used[i]<<endl;
            if ( !used[i]){
                p.push_back(nums[i]);
                used[i] = true;
                generatePermutation(nums, index+1, p);
                p.pop_back();
                used[i] = false;
            }
        }
        return;
    }

    const string letterMap[10] = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };

    vector<string> res;

    void findCombination(const string &digits, int index, const string &s){
        if (index == digits.size()){
            res.push_back(s);
            return;
        }
        char c = digits[index];
        string letters = letterMap[c - '0'];
        for (int i = 0; i < letters.size(); i++) {
            findCombination(digits, index+1, s+letters[i]);
        }

        return;
    }
};


int main() {

    int nums[] = {1, 2, 3, 4};
    vector<int> vec(nums, nums+ sizeof(nums)/ sizeof(int));

    vector<vector<int>> res = Solution().permute(vec);
//    cout<<res.size();
//    exit(-1);
    for(int i = 0; i < res.size(); i ++){
        for (int j = 0; j < res[i].size(); j++) {
            cout<<res[i][j]<<" ";
        }
        cout<<endl;
    }
//    vector<string> res = Solution().letterCombinations("234");
//
////    Solution.permute()
//    for(int i = 0 ; i < res.size() ; i ++)
//        cout << res[i] << endl;
////    std::cout << "Hello, World!" << std::endl;
    return 0;
}